/*
Source : https://leetcode.com/problems/generate-parentheses/
Author : nflush@outlook.com
Date   : 2016-08-23
*/

/*
22. Generate Parentheses

    Total Accepted: 101674
    Total Submissions: 259958
    Difficulty: Medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Subscribe to see which companies asked this question
*/

class Solution
{ // 4ms
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> ret;
        if(n) {
            char a[n * 2 + 1];
            memset(a + n, ')', n);
            //            memset(a, '(', n);
            a[n * 2] = '\0';
            generateParenthesis_helpper(a, ret, 0, 0, n);
        }
        return std::move(ret);
    }

private:
    void generateParenthesis_helpper(char a[], vector<string> &ret, int index, int min, int n)
    {
        if(index == n) {
            ret.push_back(string(a));
            return;
        }
        for(int i = min; i <= index * 2; i++) {
            a[i] = '(';
            generateParenthesis_helpper(a, ret, index + 1, i + 1, n);
            a[i] = ')';
        }
    }
};


/*
动态规划

*/
class Solution
{ // 0ms
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> ret;
        if(n) {
            string a(n * 2, ')');
            generateParenthesis_helpper(a, ret, 0, 0, n);
        }
        return std::move(ret);
    }

private:
    void generateParenthesis_helpper(string &a, vector<string> &ret, int index, int min, int n)
    {
        for(int i = min; i <= index * 2; i++) {
            a[i] = '(';
            if(index + 1 == n) {
                ret.push_back(a);
            } else {
                generateParenthesis_helpper(a, ret, index + 1, i + 1, n);
            }
            a[i] = ')';
        }
    }
};
